#include "test.h"
#include"Myers_algo.h"
#include<climits>
#include<ctime>
#include<stdexcept>
#include<math.h>

const int MAX = INT_MAX / 10000000;
const int NUMBER_OF_TEST_ITERATIONS = INT_MAX / 100000000;




int LongestCommonPrefix(const std::string& a, const std::string& b){
    return LongestCommonPrefix(a.begin(), a.end(), b.begin(), b.end());
}


void TestLongestCommonPrefix(){
    
    if(LongestCommonPrefix("baccabacaba", "abacabacaba") != 0
    || LongestCommonPrefix("abacaba", "abacabacaba") != 7
    || LongestCommonPrefix("baccabacaba", "bacaba") != 3
    || LongestCommonPrefix("aba", "abacabacaba") != 3
    || LongestCommonPrefix("bacaba", "baca") != 4){
        throw std::logic_error ("LongetCommonPrefix ERROR : wrong answer");
    }
}


int StupidDistance(std::vector<std::string>::const_iterator a_begin, std::vector<std::string>::const_iterator a_end,
                   std::vector<std::string>::const_iterator b_begin, std::vector<std::string>::const_iterator b_end){
    int a_size = std::distance(a_begin, a_end);
    int b_size = std::distance(b_begin, b_end);
    std::vector < std::vector < int > > edit_graph(a_size + 1);
    for(int i = 0; i < a_size + 1; i++){
        edit_graph[i].resize(b_size + 1);
        edit_graph[i][0] = i;
    }
    for(int i = 0; i < b_size + 1; i++)
        edit_graph[0][i] = i;
    for(int i = 1; i <= a_size; i++){
        for(int j = 1; j <= b_size; j++){
            edit_graph[i][j] = std::min(edit_graph[i][j-1], edit_graph[i-1][j]) + 1;
            if(a_begin[i - 1] == b_begin[j - 1]){
                edit_graph[i][j] = std::min(edit_graph[i][j], edit_graph[i-1][j-1]);
            }
        }
    }
    return edit_graph[a_size][b_size];
}

std::vector<std::string> GetRandomText(){
    const std::string alphabet = "ABCDEFGHIGKLMNOPQRSTUVWXYZ"; 
    std::vector<std::string> result;
    int text1_size = rand() % MAX + 1;
    for(int text1_index = 0; text1_index < text1_size ; text1_index++){
        int letter = rand() % 26;
        std::string new_string = "";
        new_string += alphabet[letter];
        result.push_back(new_string);
    }
    return result;
}

void TestEditDistance(){
    for(int test = 0; test < NUMBER_OF_TEST_ITERATIONS; test++){
        std::vector<std::string> text1 = GetRandomText();
        std::vector<std::string> text2 = GetRandomText();
        if(ComputeEditDistance(text1.begin(), text1.end(), text2.begin(), text2.end()) != 
                StupidDistance(text1.begin(), text1.end(), text2.begin(), text2.end())){
            throw std::logic_error ("Distance ERROR : wrong answer");
        }
    }
}


void TestGetXCoordinatesOfPointsWhichHaveGivenDistance(){
    for(int test = 0; test < NUMBER_OF_TEST_ITERATIONS; test++){
        std::vector<std::string> text1 = GetRandomText();
        std::vector<std::string> text2 = GetRandomText();
        std::vector<int> answer;
        answer.resize(2 * (text1.size() + text2.size()) + 1);
        int distance = ComputeEditDistance(text1.begin(), text1.end(), text2.begin(), text2.end());
        int test_distance = rand() % distance + 1;
        answer = GetXCoordinatesOfPointsWhichHaveGivenDistance(test_distance, text1.size() + text2.size(),
                text1.begin(), text1.end(), text2.begin(), text2.end());
        for(int diag = -text1.size() - text2.size(); diag < text1.size() + text2.size(); diag++){
            int x = answer[diag + text1.size() + text2.size()];
            int y = x - diag;
            if(ComputeEditDistance(text1.begin(), text1.begin() + x, text2.begin(), text2.begin() + y) != test_distance
                    || ComputeEditDistance(text1.begin(), text1.begin() + x + 1, text2.begin(), text2.begin() + y + 1) <= test_distance){
                throw std::logic_error ("GetXCoordinatesOfPointsWhichHaveGivenDistance ERROR : wrong answer %d" + text1[0]);
            }
        }
    }
}


void TestEditScript(){
    for(int test = 0; test < NUMBER_OF_TEST_ITERATIONS; test++){
        std::vector < std::string > text1 = GetRandomText();
        std::vector < std::string > text2 = GetRandomText();
        int distance;
        std::vector<std::string> edit_script = GetEditScript(text1, text2);
        int text1_ptr = 0, text2_ptr = 0;
        for(int line = 0; line < edit_script.size(); line++){
            std::string script_line = edit_script[line];
            if(script_line[0] == add_string){
                if(script_line != add_string + text2[text2_ptr]) throw std::logic_error("EditScript ERROR : wrong answer");   
                text2_ptr++;
            }
            else if(script_line[0] == erase_string){
                if(script_line != erase_string + text1[text1_ptr] ) throw std::logic_error("EditScript ERROR : wrong answer");
                text1_ptr++;
            }
            else {
                if(text1[text1_ptr] != text2[text2_ptr]) throw std::logic_error("EditScript ERROR : wrong answer");
                text1_ptr++;
                text2_ptr++;
            }
        }
    }
}


void TestFindOverlapPoint(){
    for(int test = 0; test < NUMBER_OF_TEST_ITERATIONS; test++){
        std::vector<std::string> text1 = GetRandomText();
        std::vector<std::string> text2 = GetRandomText();
        int distance = ComputeEditDistance(text1.begin(), text1.end(), text2.begin(), text2.end());
        point overlap_point = FindOverlapPoint(distance, text1.begin(), text1.end(),text2.begin(),text2.end());
        int a_index = overlap_point.x;
        int b_index = overlap_point.y;
        if((ComputeEditDistance(text1.begin(),text1.begin() + a_index,text2.begin(), text2.begin() + b_index  ) + 
                ComputeEditDistance(text1.begin() + a_index,text1.end(),text2.begin() + b_index, text2.end())) != distance){
            std::cout<<distance<<" "<<ComputeEditDistance(text1.begin(),text1.begin() + a_index,text2.begin(), text2.begin() + b_index  )<< " "<<ComputeEditDistance(text1.begin() + a_index,text1.end(),text2.begin() + b_index, text2.end());
            throw std::logic_error ("FindOverlapPoint ERROR : wrong answer sum");
        }
        if(abs(ComputeEditDistance(text1.begin(),text1.begin() + a_index,text2.begin(), text2.begin() + b_index  ) - 
                ComputeEditDistance(text1.begin() + a_index ,text1.end(),text2.begin() + b_index, text2.end()  )) > 1){
            throw std::logic_error ("FindOverlapPoint ERROR : wrong answer");
        }
    }
}

void TestAll(){
    try{
        TestLongestCommonPrefix();
        TestEditDistance();
        TestGetXCoordinatesOfPointsWhichHaveGivenDistance();
        TestFindOverlapPoint();
        TestEditScript();
    }
    catch(const std::exception &ex){
        throw std::logic_error(ex.what());
    }
}